#include<iostream>
#include<time.h>
#include<stdlib.h>
#include<vector>
using namespace std;
//版本1: 返回x应该在的位置,使<x的放左边,>=x的放右边
//以a[right]作为基准值
int partition1(vector<int>& a,int left,int right)
{
    if(left > right)
        return -1;
    if(left == right)
        return left;

    int index = left;
    int less = left-1;//维护<x的区间
    //只需遍历[left,right-1]范围即可
    while(index < right) 
    {
        if(a[index] <a[right])
            swap(a[index],a[++less]);
        index++;
    }
    swap(a[right],a[++less]);
    return less;
}
//版本2: 返回x应该在的位置,使<=x的放左边,>x的放右边
int partition2(vector<int>& a,int left,int right)
{
    //和上面基本一致,只不过代码变成了
    //当a[index] <= a[right],此时就让a[index]和less维护的区间的下一个数交换
    if(left > right)
        return -1;
    if(left == right)
        return left;

    int index = left;
    int less = left-1;//维护<x的区间
    //只需遍历[left,right-1]范围即可
    while(index < right) 
    {
        if(a[index] <= a[right])
            swap(a[index],a[++less]);
        index++;
    }
    swap(a[right],a[++less]);
    return less;
}
//版本3:<x的在左边, =x的在中间 >x的在右边
//返回:=区间的左右边界,以a[right]为基准值 
int* partition3(vector<int>& a,int left,int right)
{
    if(left > right)
        return new int[2] {-1,-1};
    if(left == right)
        return new int[2] {left,left};
    int less = left-1;//维护<x的区域
    int big = right;//维护>x的区域
    int index = left;
    //当当前数和>x的区域碰撞的时候,停止！
    while(index < big) 
    {
        if(a[index] > a[right])
        {
            swap(a[index],a[--big]);//当前数和>区域的前一个数交换,并且还需要继续考察交换之后的这个数
        }
        else if(a[index] == a[right])
        {
            index ++;
        }
        else  //a[index] < a[right]
        {
            swap(a[index++],a[++less]);
        }
    }
    swap(a[big],a[right]);
    return new int[2] {less+1,big};
}
void test1()
{
    vector<int> v;
    srand(time(nullptr));
    int n ; cin >> n;
    while(n--)
    {
        v.push_back(rand() % 100);
    }
    for(auto& x:v)
        cout << x <<" ";
    cout << endl;
    //划分
    partition1(v,0,v.size()-1);
    for(auto& x:v)
        cout << x <<" ";
    cout << endl;
}
void test2()
{
    vector<int> v;
    srand(time(nullptr));
    int n = 10;
    //cin >> n;
    while(n--)
    {
        v.push_back(rand() % 100);
    }
    for(auto& x:v)
        cout << x <<" ";
    cout << endl;
    int* a = partition3(v,0,v.size()-1);
    cout <<"小于区域: ";
    for(int i = 0;i<=a[0]-1;i++)
    {
        cout << v[i]<<" ";
    }
    cout << "等于区域： ";
    for(int i = a[0];i<=a[1];i++)
        cout << v[i] <<" ";
    cout <<"大于区域: ";
    for(int i = a[1]+1;i<v.size();i++)
        cout << v[i]<<" ";
    cout << endl;
}
int main()
{
    //test1();
    test2();
    return 0;
}